#include <stdio.h>
#include <time.h>
#include <ctime>
#include <stdlib.h>


void heaplize(int* v, int sz){
	bool complete = true;
	for(int i=0;i<sz;i++){
		//branch1
		if((2*i+1) < sz){
			if(v[i] < v[2*i+1]){
				complete = false;
				int tmp = v[i];
				v[i] = v[2*i+1];
				v[2*i+1] = tmp;
			}
		}

		//branch2
		if((2*i+2) < sz){
			if(v[i] < v[2*i+2]){
				int tmp = v[i];
				v[i] = v[2*i+2];
				v[2*i+2] = tmp;
				complete = false;
			}
		}
	}

	if(complete == false){
		heaplize(v, sz);
	}
}

void heapSort(int* v, int sz){
	if((sz-1) == 0) return;

	int tmp;
	tmp = v[0];
	v[0] = v[sz-1];
	v[sz-1] = tmp;

	heaplize(v, sz-1);
	heapSort(v, sz-1);
}

int main(){
	srand((unsigned)time(0)); 
	const int sz = 10;
	int v[sz];
	for(int i =0; i < sz; i++){
		v[i] = rand() % 100;
		printf("%d ", v[i]);
	}
	printf("\n");

	heaplize(v, sz);
	heapSort(v, sz);


	for(int i =0; i < sz; i++){
		printf("%d ", v[i]);
	}
	printf("\n");
	return 0;
}
